Криптосистема Бенало

Криптосистема Бенало — модификация криптосистемы Гольдвассер — Микали. Основное их отличие состоит в том, что криптосистема позволяет зашифровывать блок данных единовременно, в то время как в схеме Гольдвассера и Микали каждый бит данных шифруется отдельно.

Разработана Джошем Бенало в 1988 году. Получила применение в системах электронного голосования.

Система является частично гомоморфной. Как и во многих криптосистемах с открытым ключом, эта система работает в группе [math]\displaystyle{ \mathbb( {Z} /n\mathbb {Z} )^{*} }[/math] , где [math]\displaystyle{ n }[/math] — произведение двух простых чисел.

Описание алгоритма

Генерация ключа

1. Выбираются блок размера [math]\displaystyle{ r }[/math] и два больших различных простых числа [math]\displaystyle{ p }[/math] и [math]\displaystyle{ q }[/math], удовлетворяющие следующим условиям:
   1. [math]\displaystyle{ r }[/math] и [math]\displaystyle{ (p-1)/r }[/math] — взаимно простые ;
   2. [math]\displaystyle{ r }[/math] и [math]\displaystyle{ q-1 }[/math] — взаимно простые.
2. Вычисляется [math]\displaystyle{ n = p \times q }[/math], [math]\displaystyle{ \phi =(p-1)(q-1) }[/math];
3. Выбирается [math]\displaystyle{ y\in \mathbb {Z} _{n}^{*} }[/math] так, что [math]\displaystyle{ y^{\phi /r}\not\equiv1\mod n }[/math].
   Замечание: если [math]\displaystyle{ r }[/math] составное, то вышеуказанные условия не являются достаточными для обеспечения правильной расшифровки, то есть для того, чтобы всегда выполнялось [math]\displaystyle{ D(E(m))=m }[/math]. Чтобы избежать подобного, предлагается выполнять следующую проверку: пусть [math]\displaystyle{ r=p_{1}p_{2}\dots p_{k} }[/math]. Тогда [math]\displaystyle{ y }[/math] выбирается таким образом, чтобы для каждого [math]\displaystyle{ p_{i} }[/math] выполнялось [math]\displaystyle{ y^{{\phi /p_{i}}}\neq 1\mod n }[/math] .
4. Пусть [math]\displaystyle{ x=y^{{\phi /r}}\mod n }[/math];

Тогда открытым ключом является [math]\displaystyle{ (y,r,n) }[/math], а секретным ключом — [math]\displaystyle{ (\phi,x) }[/math].

Шифрование

Шифрование сообщения [math]\displaystyle{ m\in {\mathbb {Z}}_{r} }[/math]:

1. Выбирается произвольное [math]\displaystyle{ u\in {\mathbb {Z} _{n}^{*}} }[/math];
2. Тогда [math]\displaystyle{ E_{r}(m)=y^{m}u^{r}\mod n }[/math].

Расшифрование

Для начала заметим, что для любых [math]\displaystyle{ m\in {\mathbb {Z}}_{r} }[/math] и [math]\displaystyle{ u\in {\mathbb {Z}}_{n}^{*} }[/math] выполняется: [math]\displaystyle{ a=(c)^{{\phi /r}}\equiv (y^{m}u^{r})^{{\phi /r}}\equiv (y^{{m}})^{{\phi /r}}(u^{r})^{{\phi /r}}\equiv (y^{{\phi /r}})^{m}(u)^{{\phi }}\equiv (x)^{m}(u)^{0}\equiv x^{m}\mod n }[/math]

Таким образом, чтобы вычислить [math]\displaystyle{ m }[/math], зная [math]\displaystyle{ a }[/math], проводится операция дискретного логарифмирования из [math]\displaystyle{ a }[/math] по основанию [math]\displaystyle{ x }[/math]. Если число [math]\displaystyle{ r }[/math] небольшое, возможно нахождение [math]\displaystyle{ m }[/math] через исчерпывающий перебор, то есть проверкой выполнения равенства [math]\displaystyle{ x^{i}\equiv a\mod n }[/math] для всех [math]\displaystyle{ 0\dots (r-1) }[/math]. При больших значениях [math]\displaystyle{ r }[/math], нахождение [math]\displaystyle{ m }[/math] можно проводить с помощью алгоритма Гельфонда — Шенкса (алгоритм больших и малых шагов), получив временную сложность расшифрования [math]\displaystyle{ O({\sqrt {r}}) }[/math].

Расшифрование шифртекста [math]\displaystyle{ c\in {\mathbb {Z}}_{n}^{*} }[/math]:

1. Вычисляется [math]\displaystyle{ a=c^{{\phi /r}}\mod n }[/math];
2. Подбирается [math]\displaystyle{ m=\log _{x}(a) }[/math], то есть такое [math]\displaystyle{ m }[/math] , что [math]\displaystyle{ x^{m}\equiv a\mod n }[/math]

Свойства криптосистемы

Гомоморфизм

Криптосистема Бенало гомоморфна относительно операции сложения:

[math]\displaystyle{ {\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})=(g^{x_{1}}u_{1}^{r})(g^{x_{2}}u_{2}^{r})=g^{x_{1}+x_{2}}(u_{1}u_{2})^{r}={\mathcal {E}}(x_{1}+x_{2}\;{\bmod {\;}}r) }[/math], где [math]\displaystyle{ {\mathcal {E}}(x) }[/math] является функцией шифрования от сообщения [math]\displaystyle{ x }[/math]

Стойкость

Стойкость криптосистемы Бенало основана на труднорешаемой задаче о вычетах высокой степени. Зная размер блока [math]\displaystyle{ r }[/math], модуль [math]\displaystyle{ n }[/math] и шифртекст [math]\displaystyle{ E(M) }[/math], где разложение на множители числа [math]\displaystyle{ n }[/math] неизвестно, — определить открытый текст вычислительно сложно.

Литература

1. А. И. Трубей «Гомоморфное шифрование: безопасность облачных вычислений и другие приложения (обзор)»
2. Benaloh, Josh (1994) "Dense Probabilistic Encryption"